package net.tp.algo.sort;

/**
 *
 * <p>Radix Sort.</p>
 *
 * <p>Numbers need to be partitioned into negative numbers and non-negative numbers before sorting. Otherwise, negative numbers appear
 * to be larger than non-negative numbers. Sorting negative and non-negative numbers follow the same algorithm.</p>
 *
 * <p>Given the radix bits (e.g. 4 bits), the quick way to compute the mask is {@code (1 << radixBits) - 1}.</p>
 *
 * @author Trung Phan
 * @time $O(n)$
 * @space $O(n)$
 *
 */
public class RadixSort {

    public static void sort(int[] data) {
        sort(data, true, 4);
    }

    public static void sort(int[] data, boolean asc, int radixBits) {
        if (radixBits < 1 || radixBits > 16) {
            throw new IllegalArgumentException();
        }

        int p = partition(data);
        int[] buf = new int[data.length];
        sort(data, buf, 0, p - 1, asc, radixBits);
        sort(data, buf, p, data.length - 1, asc, radixBits);

    }

    private static void sort(int[] data, int[] buf, int lo, int hi, boolean asc, int radixBits) {
        if (lo >= hi) {
            return;
        }
        int[] source = data;
        int[] target = buf;

        int radix = 1 << radixBits;
        int mask = radix - 1;

        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int i = lo; i <= hi; i++) {
            if (min > data[i]) min = data[i];
            if (max < data[i]) max = data[i];
        }
        int maxBits = 32 - Math.min(Integer.numberOfLeadingZeros(min), Integer.numberOfLeadingZeros(max));

        for (int shift = 0; shift < maxBits; shift += radixBits) {
            int[] counts = new int[radix];

            for (int i = lo; i <= hi; i++) {
                counts[(source[i] >>> shift) & mask]++;
            }

            if (asc) {
                for (int i = 1; i < counts.length; i++) {
                    counts[i] += counts[i-1];
                }
            }
            else {
                for (int i = counts.length - 2; i >= 0; i--) {
                    counts[i] += counts[i+1];
                }
            }

            for (int i = hi; i >= lo; i--) {
                target[lo + --counts[(source[i] >>> shift) & mask]] = source[i];
            }

            int[] tmp = source;
            source = target;
            target = tmp;
        }

        if (source != data) {
            System.arraycopy(source, lo, data, lo, hi-lo+1);
        }
    }

    /**
     *
     * Partition data into positive and negative numbers before sorting.
     *
     * @param data
     * @return
     */
    private static int partition(int[] data) {
        int lo = 0;
        int hi = data.length - 1;
        while (true) {
            while (lo <= hi && data[lo] < 0) lo++;
            while (hi >= lo && data[hi] >= 0) hi--;
            if (hi < lo) {
                return lo;
            }
            swap(data, lo, hi);
        }
    }

    private static void swap(int[] data, int i, int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

}
